﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LightCAD.MathLib.CSG
{
   class UnionFind
    {
        private List<int> ids = new List<int>();
        private List<int> rank = new List<int>();

        public UnionFind(int N)
        {
            this.ids.makeSize(N);
            this.rank.makeSize(N);
            for (int i = 0; i < N; i++)
                ids[i] = i;
        }

        public int find(int i)
        {
            int id = i;
            while (ids[id] != id)
                id = ids[id];
            ids[i] = id; // path compression optimization
            return id;
        }
        public int unionIds(int i, int j)
        {
            int iid = find(i);
            int jid = find(j);
            if (iid == jid) // no need to merge the same tree with itself
                return iid;
            // simple implementation (not used)
            // return ids[iid] = jid;
            // instead we attempt to rank balance
            if (rank[iid] > rank[jid])
            {
                return ids[jid] = iid;
            }
            else if (rank[iid] < rank[jid])
            {
                return ids[iid] = jid;
            }
            else
            { // equal ranks
                rank[jid]++;
                return ids[jid] = iid;
            }
        }
        public List<int> dump()
        {
            var result = new List<int>();
            result.makeSize(ids.Count);
            for (int i = 0; i < ids.Count; i++)
                result[i] = find(i);
            return result;
        }
    };
}
